N=3000;
m1=8125;
m2=1231;
S=[32323,13,1,1,1,1,25237,1,143315,10900331,36523,1,1350619073,27077,1,936032819,1,1,1091129,19309,1,55469,323465,1694193247,1,364885,255222491,98953,32173,1233559777,1,1,25163,57791,13,28031,13,1,13,5,1,1,1,13,42083,48857,22369,1813185973,1,2797,5,1,157835,26392567,13,1,1,282494761,1949,11273,13,209915,1112157649,65315,13,71741,1,1,1,1557320873,1,13,5,13,119459,727256261,146747509,8219,5,13,1,56239,67789,1,469055,13,13,92857,1,869626411,51977,5,1546285,1,1,1,1,1289,51133,67251197,55681,1,13,13,5525117,16481,1,6079385,19073,1,25457,1,134105,1,13,86287,406164589,1089520279,748659341,1485265615,61409,1,50439919,10607,1889,159905,35963,12941,1,1,87679,181765,5,1644350563,1,1,61547,8933,30937,1,67589,1,40823,1,85733,49033,373139,5,1,1,11369,666048749,1,9027449,24989,1,728533,184495,79481,90121,64709,71777,31991,271885,80629,22817,1,95111,92467,1,5,34781,1,13,51971,16619,641329,381984973,1,23563,175450819,1,666931211,1027944143,1,5,417883237,43261,51347,982033,1,13,1257581,16921,83341,23669,147055,1,1,1,1,1,49985,961706189,90379,79279,389467,25,1,1,1,1,1,13,538322237,1,28109,1,91151,335284441,77801,28211,1,854191,1,447995,81929,3469,74215,1,539275657,1259395099,1058008759,1,1192185767,21503,479,1513982221,1197443,122603,48197,1,1,1960582993,1,35059,54751,15797,32159,1,13,1,1,1,1,1,418085,23929,1,3767,1,1,1,1,1,1,83077,71249,39671,1,1,776009,872989,1,1,1,21169,64439,39847,15319,60259,1,1,1,4452643,80779,13,1,72503,1,98807,1413297979,59029,1,715035179,1,37363,1,1,87959,1,1,13297,1,59021,1279295117,1,66221,36457,57899,234866377,448684787,1,1306692161,1,21383,5,6977,1,12755,1,1014625921,72155,1,1,1,7603,12923,1,81619,1,1,1,78511,1,1,45191,304435,1,1,57697,979946483,88129,1,2053,40591,91577,22637,5827,1,24109,1020617,1,1,417962047,1,1,3881,190977817,1,1,1,1,1,12097,73181,1,5,324455,1,28649,82571,1,1,520819,1,61345,1,49043,1,41281,1,1481,198772199,1,24533,1,253355,569179,1023409237,1,1,89101,1133450033,1,7679143,1,1,43481,344199883,39569,1,33329,643981,1,1,1,20177,1,40169,24049,95203,1,39847,46171,1,1,13,68443,1,5,79777,1781122789,1,95419,381448549,13,1,1,95393,744600847,604322461,53027,17041,362395619,68771,14779,12517,22093,4339,1812510151,77761,48049,1,1,1,27647,1,1,49627,849146149,5,19813,1,1,12842141,159198791,63599,1,1,14867,718489469,35977,1,79867,58061,13,3313,1,1069788953,13,1238586091,10889,54539,13,42751,1,1,4871,1,1,1,4951,1,1,1,1860460849,1,204503,44777,54713,34847,38977,1047491857,64661,93001,7589,562911301,13645427,1,1115435507,167845,22483,1,17093,79063,1290601,92957,43207,1,1,1,1414123547,5,1609111969,211615,18617,30341,47939,1,30517,43234489,1,1,1,24179,86293,4453865,95131,23,1,1,92387,1,1,1,1,383486591,3851,65,1,1,5,1,25463,68581,850110307,482766419,5,2531,1,90997,1,13634725,6131,1,483685,73951,1,13,45119,1,13,31991,1,1234493,4357,239589149,5,385333,45763,5,1,11177,25981,337357187,1997447449,640712537,88211,1,1,12413,31513,57413,1,1,56531,4835,1,81349,82651,381583339,1,1,62585,6779,1,1,1,1,62191,1,1,86929,1,53047,126917407,3451565,35591,621803383,1,1,85081,1,1,947791,392545,21143,65011,5,1,1,15427,1,21067,90947,327457,178385,1,1,1,1,1,97459,1,644783057,20899,1281631499,1,81497245,1,1546640633,1,1,1,81533,70139,63397,75169,1284803567,5,38569,1,666048505,1,1757829065,94253,1865471917,8135,36923,5,1,13,1,41443,71821,17509,13,61717,1,1,1,59357,176555,1,60497,1,1,26209,23899,70759,1,38197,8194979,1750340707,1,1,5101,1842227071,1,231512569,1,58885,1,94463,751231,13,1,1,13,1,17291,13,91151,1,198419,85297,19891,5,13,65371,1,30323,1088125553,1,1,13,1,43313,1,1492131677,2609,1,25849,37321,88463,83059,1,31981,97829,1,4603,1,1,1,1,193615,24499,1,20149,1,1,34841,20479,1,1,793663,1978263587,196937,25939,12277,17955925,5741,225667,5,41611,31873,5,32771,1228356497,60763,1138735,393846911,26665,5,68639,404733733,13,1,243228247,5,1,169,1,1,70207,1,1,79153,1,5,52285,5,7759,31271,97859,47737,395129663,94559,1,47129,1,240539,10271,13,36847,793321603,1220463323,1,81563,1,304967,82939,13709,1,1,71999,3989,425191,5,281021,13,51217,56087,1,13,33349,1,1,47843,1,1,74324801,2731495,70373,1,7487,5,36433,4339,169,80233,79301,1,1,743075,1,6619,1,1,496863761,6653,1,665130943,41057,32713,1597929673,13,13,1,55633,362485,1380457427,87181,42139,705263,35311,29789,60497,24677,44549,1,1,5,8219,33617,969031793,79829,63841,1769364581,13,302190509,1,5,876473,1,16747,1,41183,1,643281577,1,1006798241,67329853,1,687819497,1,1,80629,1,253033771,1,307355,84143,1,1,27793,72077,1,1987,89567,1,20731,1,89017,1,1,25,964070057,1,1,1,33569,1,1,13649,12301,49463,1,1,1,65701,38783,1,13,5,27611,92863,1,59159,87403,13,13,88937,1,1,588458837,38453,91757,818099593,54721,1,1,1,13,1,712777,1,1,1,126726701,7877,1,972959,744956749,46993,184165,267185,85223,57731,1,1,1,22469,1,9371,1,1,1840987549,65579,1,83267,762827,1591434931,870918479,13,1,2851,228449,121330571,883259,90053,127656211,1,202163,715658117,1229,206215,170907887,551291,103745,1,1,1,765413977,1,390057361,1,34285,12781,330145,394371889,66931,1,1,1,1,1,133246171,65,7207,1,84857,1,1,63211,46679,590698951,97117,15493,973409117,12379,111385,63367529,469401323,10753,1,1,61879,10214881,588757,158755,15767,52145,1,90745,73583,1,99367,1,90499,1,1,70663,1,407251,1827240097,1,1,1,1215082879,5,43933,51431,10861,43691,1,1,1,171152621,29399,317335,1,1,1,1,1,1,5,604301443,92269,96353,88547,40933,5,1,27061,1,987642697,161635,1,70141,57191,14293,1,76091,1,61543,508807,1,1,1,55547,1,88129,13,628425359,34127,89681,13841,5,99089,1,1,1,10859,105701279,67121,1975176527,13,14957,773415659,1,1,56911,1,35933,93133,73939,1407633343,49121,46337,93787,13,1,5039,392965,38861,362405,5,1,1,92311,1,230590949,390835,1,71341,4157,1650991049,505172743,1,19507,1177865743,1,25799,1,1,705620815,28349,1081639,315485,969087677,8933,6151,1,38069,25649,1,22621,195815,141901049,41543,81281,1,1017428347,18121,86477,1,82613,1,1,1,5,1,1,1,1,1,75289,49103,213236329,1,1,48497,1,80833,47981,57601,1,1,1,21799,35617,49417,1,1,1,95813,1,1422263543,1,79691,24151,1,36131,347874721,7451,1,65699,77569,2308085,1,44809,30697,9049,1,1,12577,68095,21937,59281,5,1,1911394787,1,1,14639,1,1,1,1294792327,1,19889,42391,5,91381,60869,13,1,159601,640393,55411,94117,1,41603,282971,1,1,1,13,65099,425003659,1,13,44838737,1,403389409,1,32027,1,1447938509,24029,23537,1,60923,1,22783,1,1,5,93913,73720847,1,1,31699,1,967290713,1,944749,63067,16529,50707,1,1,57097,747877,1,1,1,1,5,1,1,1,138365,1,28631,1,1,1,84131,315924127,1988543423,15907,65239,19231,13,140193929,96643,1,25,1,1,1,84017,1,401609,1,19469,1,1,34439,57601,91835,94841,27733,64123,1,1,93901,39461,1,13,1,290335,13,96281,10949,82913,805252607,54001,78901,1,1,22621,12511,93809,639640753,1,229745,2351,72797,5,34583,65839,13,2267,95413,54049,1,73794785,614242471,1,84347,46199,5,1,1021196567,1,1,1,1,11743,52541,1,5,613,75659,1,46349,74419,1,77509,51361,1,5,1,1,89989,22709,85513,1642893709,1,92789,1,49603,13,3637,41941,65141,1993,1,1,1,1079916269,1,12343,1,5,5,1,3631,1,46589,1,23057,1,593466409,74065,1215029713,595769789,406289,2399,1,16176173,99833,4129,28751,13,1,1,647301493,1,83575,1,1,1,1,1,1,58481,46952413,1,16553,73961,1,13,5,13,1,5,1,14813,10601,5,66949,1,69011,1,1,5,74587,1,62705,1504175,48187,220783313,1,1,5,1,50261,1,10673,1271786233,13,1,1,1,1,311,1,21319,25163,61493,1,1,1,1,1,1,950401339,1,35537,1,1,2657135,59021,1,1,1,1,1,25703,5,1,5351,5,75883,1,511458611,66979889,1,1902502531,120005,394433093,95773,1,397685,1,1,37423,5,13,86183,31399763,68071,13,1,3212789,1,66067609,57119,49003,1,1,1,4523,1,1,1,1,5101,1,92791,1,463,1,13,1,1661105051,468871,27239,13,68280461,33587,1,223361753,65555513,119446013,13,203593,1,5,30491,14629,487591,1,9001,1,1,327115,1,1,597325,87481,1,37339,429572593,1,1231009,13,43759,23567,1964108969,57733,9241,1157897,1143165673,76801,1,486295,179856727,25609,91381,13007,5,169716431,99487,78367,13,5,73679,13,1,1,1,591637223,1,47459,25643,443270923,1,22643,4283,61051,1,1,22877,13,29567,1,54347,32885,821439041,1230575,1,66949,28571,1,13,4967,90529,25121,1,50359,8059,96517,7639,1,1638462979,126246871,474353951,235205,12117089,39499,521287,1,1,607980371,4621,12197,1,1,52501,1,1,1,5,2341,1766383679,80071,1,469895,1,25057,1,761371,13763,1113549407,674891689,41621,1,1,67499,1,3697,13,40214641,1841071579,173435,1,51637,89231,33757,1,435755,3863,1,1,5,26683,80747,17351,598585,98627,12713,6373,59351,1909052347,953,83177,1,1,398495,84319,167999,1,1,113195,8263,162245231,1,50539,36683,1,95569,16103,368755,1,71123,102988337,986906197,1,77773,329915,13,17807,38711,86813,1,59797,13,5441,1,5,1493,1422045397,74707,1,223855,1,79693,12409,34919,65,4111,212901107,1,1,57719,1,13,1,845923,1,1,711341153,633253919,74377,13723,261255763,1,86027,34781,347214359,1981002319,78301,5,13,70537,1,33071,91009,11897,41507,13,44497,112205,703784399,1,13,3299,1031710753,85999,14765,1,55061,4699955,67961,1,22751,73141,9721,3923,80077,1,1,21383,1,1,1,1,1,13,1,1,20051,1,49207,1,22109,1,1,85931,1,1,1708964951,124093537,127439,1,1,1,1,1,1,9371,1,70981,79379,89449,1,13,8848241,36479,373977553,1,1,351205,870936431,86509,1,1,5,11489,21881,1,1,197249,380155,1,592118047,1,1,29191,1,1,79279,1377370469,95143,37781,431215,1,1,1,64879,32029,519618119,201279341,1,21107,1,123736631,1,26768153,58211,1,1,1,3307,1,13,13,1068859279,1,1,49531,13241,5,36433,1236925,1,286770719,28163,74143,30467,1,684440299,86951,1,165535,82457,1,1926359579,33179,13,88469,1419164479,74897,57173,1,13,45439,1,1,1,1,62791,770107,99871,1,13,1,993831323,1,35831,408411917,1,81727,210785,1,15473,1,1,7853,48341,1,65,1,36899,58453,86539,30709831,26513,1,1,1,88721,1,1,26113,13,5,85621,422028767,35257,836329,50329,13,13,58147,55441,51673,3547,44357,33317,27631,17749,1,95959,30671,937,68507,1,83077,93889,27067,1,14831,63467,571747763,1,55807,2689,1,13,82301041,1,1,73043,62659,16349,1,1,925329953,1,22531,1834218679,1,1272193,1,1,47353,58211,340186163,1,1,55679,1,31657,95561,120111373,42193,1,77339,1,96199,4831,1,173155,1,58699,1,36677,1,1,50069,1,1,171379,1,8779,356765,782326373,5,71867,90547,68071,5507,1,1150669,13003,1,996437,1,366536509,1,80911,300205,1,13,1,4999,1,1,13,54437,1,1563669403,1,1,38067977,35053,1933,11941,1,34673,55529,283768769,1,5,1,84263,60127,1,123982823,5,192149987,96157,59539,1,20297,67559,1,1,1,57557,1,146291059,1,1,31391,1,98369,1,1,47869,1,27617,1,1,5,21863,33289,98011,40351,56929,70949,721831427,96079,22717,1429,13,1,1,457873,55399,1,13,1,206557751,62591,33347,1,9161,1,1,1,93199,5,1,1,95131,43651,1,1,1,1,79670231,24907,13,16427,1105626733,91097,59149,5,1,1050936409,1,1,1,4802395,86197,2220425,1,994409,1,42379,187499,5,1,1,1176957643,140120503,13999,636116633,1,1367297443,1,5,14009,92353,1,1,356161,5,57853,1,50627,12799,22769,25523,88345,36923,1,124732781,315856763,46559,49253,1,1,1,1,1,5,1,27131,13,1112761,1,1,1,1,93481,1,77849,1,220727,1,2239,1,1,1,42257,1621579483,1,85331,52951,5,1483761863,252629,83497,1,1,68053,327245,51217,31147,7817,702624577,80677,1,1,1,1,78259,88037,1,446930263,1,1,126373,1893279629,1,13,374904389,1199109811,286386071,3623,169,1,3613,1,18805,5,57259,74894387,46959487,1,1,971269,71453,1,1,1,1,5,23857,97609,62213,1,5,306787,1,5541491,50503,22171,1,1,1,13,51287,902603,1,1,1,1,13,8016317,88169,43624003,1,1035262819,1,5,1,81353,1,11827499,211941179,557922193,64937,1,68329,28019,106915,1,65,98251,1,1,1,1363971061,1,1,715023061,56911,1,86693,1,54502523,88259,16249,1873,1,115985,1804830317,16476701,5,1,24683,895929127,1,86587,32719,1,952852787,263785,1,75041,17299,373232791,988039,77029,1,1,1,1,5,381065,1,2145925,1168271,1,850109,55333,86113,32077,44521013,1,436585,1279057,1,1077434003,1,90887,1,1,43517,1,1,17939,242114413,1,37993,53777,1,87793,1,70289,26261,13,37,563,1,13,1,1,499945,327746303,34807,290155,1,1,1197672143,1,1,1,991367,1,36319,1,55355,49369,85091,722111,99119,11887,1,25,1,1547040637,1,1293741677,459719,5,7541,1,1160939,1,1,5,1,1309775,1,74759,1875633805,877357,1,5,5,83299,66809,1,1,11329,93851,1,288189817,13,57317,288942593,1,556135721,1,1,14153,5,1,16301,1,1,76837,8417597,1,4241,51197,67489,13147,911169409,1,22501,484733831,1,169992799,78893,79987,42181,1,1,1,1,467,5,23311,1,1,91369387,349583,330545,48589,38331193,10667,1358906057,1,5,92863,450203,1,36241,1,1,1,23291,29429,377695,240577567,6263,5,114605,71591,444314797,1016041,1,11933,706464659,13,1,5,1,98251,5189,21433,1,1,1,569257,955452277,90595,5,1,34347059,1,1,36433,36529,327197,13,1,1,1,1,92033,1,60689,1,1,1,1,57179,284485,1,1,330715897,1,53503,67139,1,1,1,1,1,46171,1,10242583,95701,1,184645,809,371423,1,1320324661,654614965,1,1,1,13,1,1,38545,1,63689,243395,3109,1,1,36697,1,283565,1,1,62081,89417,930761773,5,8389,1,76541,75583,883909,105055,1671313901,1,80153,1,100715,284453,130885,474050573,53617,67139,1,26561,23039,22067,91199,674442211,20177,1268137,1,95959,33603301,1,1,456989,1,1,1,13,1,95471,1,1,582023,13,67679,87931,1,968171411,528613607,1,1132683037,1,1,13,17705,1,33857,1,170705,1,68531,34759,16683911,5,32345,1,1,5,1,1,1,52237,21991,303251,1,13,26086237,10957,1,13,43013,628823,1,28201,65,1723086157,27541,39623,32603,1,12857191,41639,1,606619,1,1889393083,146865137,50069,40168049,1,1,1358549243,1,1,5,84181,52361,1,79901,1,259961,1,1,1,1,13,35149,1,1,1,50221,1298666801,75679,1838178229,1,12503,1,50543,1,60661,14029,13,5849,13,77889599,1,70951,3109,1,78797,20873,50923,1,1,77731,80233,1,1,13,181835411,191994977,1,5,73939,1,74009,56077589,143338463,1,1,1,1,1,1,80743,810478681,74455,1,1,648022579,181129,1,77471,1,856973,1,1,1,1669,1,31643,842042645,1,72613,26995,1,40163,1477693001,296755,1,1,67757,1,1,1,22013,1,90401,726400471,1,11813,982033,1,13,1,49477,1,1,1,133415,56113,1,1,89633,778359079,1,47287,20341,1,66653,1,39619,1,1,75347,1,86249,1,1,5,1,1,13883,1,444840763,1,1,1975382923,1,1,44645969,9973,43649,5,5,13,1,1,1,1,162147059,56269,1,1,21563,1,1931,47699,1,62131,668098129,1,1,5,164567,593983,1,1,9580103,1,15923,79063,1,1,1,1,1,29531,1,1,1,42281,1,5688637,35801,1,1,77265121,68071,64303,11471,1,47513,1,1,1,30497,5,197,1,26647,1,36677,5,1,1,401297,15923,717775,1,1,1,1,13,233,1,3613,1093626767,26681,93047,1,33937,34543,1,1,1,1,1,80953,28901,8627,874003,77383,1,1,41453,65,1,13,1,17645,2132597,1,13,1,31699,5,87767,169,65053,1,1,1787485559,1,65,2393,113289527,1152122563,1,126605,38749,1,1,1,57977,1,923263279,69763,686820271,65927,11399,5,1,28859,243315131,86923,36013,673231,44819,1,1,26951,1,1072019,33645841,87545,1494390397,1901624359,96973,37547,1,457,698054453,1,1,62701,34543,1,23039,72287,1,1,1,1,1,1,21613,1,99689,1,51001,1,1,1,86837,1,1,28751];